package org.example;

import java.util.HashMap;
import java.util.Map;

//实现 LRUCache 类：
//LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存

//int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

//void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；
// 如果不存在，则向缓存中插入该组 key-value 。
// 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

//函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

//最近使用的移动结点到头部
//最久未使用的节点放到链表尾部
public class LRUCache {
    //定义双向链表节点
    class DLinkedNode{
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;

        public DLinkedNode() {
        }

        public DLinkedNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    //定义hashMap
    private Map<Integer, DLinkedNode> map = new HashMap<>();

    private int capacity; //最大容量
    private int size; //当前大小

    private DLinkedNode head, tail;//定义虚拟头尾节点
    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkedNode node = map.get(key);
        if(node == null) return -1;
        // todo 标记为最近使用
        moveToHead(node);
        return node.value;
    }

    //void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；
// 如果不存在，则向缓存中插入该组 key-value 。
// 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
    public void put(int key, int value) {
        DLinkedNode node = map.get(key);
        if(node != null){
            node.value = value;
            moveToHead(node);//标记为最近使用
        }else{
            DLinkedNode newNode = new DLinkedNode(key, value);
            map.put(key, newNode);
            // todo 添加到链表头部
            addToHead(newNode);
            size++;
            if(size > capacity){
                //逐出 最久未使用的关键字
                DLinkedNode removed = removeTail();
                map.remove(removed.key);
                size--;
            }
        }

    }
    //链表操作方法

    //添加节点到头部
    private void addToHead(DLinkedNode node){
       node.next = head.next;
       head.next.prev = node;
       head.next = node;
       node.prev = head;
    }

    //移动某节点到头部
    private void moveToHead(DLinkedNode node){
        //先移除再添加
        removeNode(node);
        addToHead(node);
    }
    //移除某个节点
    private void removeNode(DLinkedNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    //移除尾部节点
    private DLinkedNode removeTail(){
        DLinkedNode removed = tail.prev;
        removeNode(removed);
        return removed;
    }

}
